#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

template<typename E>
//qsort is also a function in Linux
class QSort
{
public:
	QSort(E datalist[], int size)
	{
		dataArray = datalist;
		performQSort(0, size - 1);
	}

	void performQSort(int leftindex, int rightindex)
	{
		//Don't perform sort for only 0 or 1 elements.
		if (rightindex <= leftindex)
			return;
		int pivotindex = findpiviot(leftindex, rightindex);

		//Put the pivot at end:
		swap(pivotindex, rightindex);
		//k is the first position in the right subarray:
		int k = partition(leftindex - 1, rightindex, dataArray[rightindex]);
		swap(k, rightindex);
		performQSort(leftindex, k - 1);
		performQSort(k + 1, rightindex);
	}//end constructor

private:
	E * dataArray;

	inline int findpiviot(int leftindex, int rightindex)
	{
		return (leftindex + rightindex) / 2;
	}//end function: Find piviot.

	void swap(int indexSt, int indexTg)
	{
		E temp = dataArray[indexSt];
		dataArray[indexSt] = dataArray[indexTg];
		dataArray[indexTg] = temp;
	}//end function: Swap elements.

	inline int partition(int leftindex, int rightindex, E & pivot)
	{
		do{
			//Move left index right, when in reverse order.
			while (dataArray[++leftindex] < pivot);
			//Move right index left, when in reverse order.
			while ((leftindex < rightindex) && (pivot < dataArray[--rightindex]));
			cout << "Pivot: " << pivot << endl;
			cout << "Left number switched: " << dataArray[leftindex] << endl;
			cout << "Right number switched: " << dataArray[rightindex] << endl;
			swap(leftindex, rightindex);
		} while (leftindex < rightindex); //Stop when left index is bigger.

		return leftindex;
	}//end function

};//end class: Quicksort. 